"""
知识模块
• Python 编程语言
知识点
• 递归
• 分区操作
• 列表操作
• 算法复杂度分析
受众
• 初级测试开发工程师
• 初级Python开发工程师
作业要求
编写一个Python程序，实现快速排序。
解题思路
1. 首先选择一个基准元素，通常是选择待排序列表的第一个元素。
2. 将列表分成两部分，小于基准元素的元素放在左边，大于基准元素的元素放在右边。这个过程称为分区（partition）。
3. 递归地对左右两个分区进行快速排序。也就是将左边的分区作为新的子列表，再次选择基准元素，并进行分区操作。对右边的分区也是同样的操作。
4. 递归的结束条件是分区中只有一个元素或为空，此时分区已经是有序的。
5. 最后将所有的分区合并起来，即可得到排好序的列表。

"""

def quickSort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[len(arr) // 2]  # 选取数组中间元素作为基准值
    left = [x for x in arr if x < pivot]  # 小于基准值的部分放在左边列表
    middle = [x for x in arr if x == pivot]  # 等于基准值的部分放在中间列表
    right = [x for x in arr if x > pivot]  # 大于基准值的部分放在右边列表

    return quickSort(left) + middle + quickSort(right)  # 合并结果返回


arr= [12,3,5,56,6,7,7,8,8,3,3,4,34,53,5,56,35]


na = quickSort(arr)

print(na)